package 蓝桥杯算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class day15 {
    public static void main(String[] args) {
        day15 a = new day15();
        int[] num = {1, 2, 3, 5};
       /* System.out.println(a.findsort(num, 6).toString());*/
        String s="aabbccbbaa";
        System.out.println(a.partion(s).toString());


    }

    List<String> list = new ArrayList<>();

    public List<String> comninations(String digital) {
        if (digital == null || digital.length() == 0) {
            return list;
        }
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqs", "tuv", "wxyz"};
        backing(digital, numString, 0);
        return list;
    }

    StringBuilder result = new StringBuilder();

    public void backing(String digital, String[] numString, int num) {
        if (num == digital.length()) {
            list.add(result.toString());
            return;
        }
        String str = numString[digital.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            result.append(str.charAt(i));
            backing(digital, numString, num + 1);
            result.deleteCharAt(result.length() - 1);
        }
    }

    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> findsort(int[] num, int key) {
        Arrays.sort(num);
        backTracing(res, num, path, key, 0, 0);
        return res;
    }

    int sum = 0;

    public void backTracing(List<List<Integer>> res, int[] num, List<Integer> path, int key, int sum, int begin) {
        if (sum == key) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < num.length; i++) {//begin的改变在这次循环中
            if (sum + num[i] > key) {
                break;
            }
            path.add(num[i]);
            backTracing(res, num, path, key, sum + num[i], i);//跟着循环改变
            //结束一次大循环的时候，begin会自动添加
            path.remove(path.size() - 1);
        }
    }

    //path的数据结构创建有误

    List<List<Integer>> res1=new ArrayList<>();
    LinkedList<Integer> path1=new LinkedList<>();//队列
    public List<List<Integer>> combaine(int[] nums,int target){
        Arrays.sort(nums);
        backTracing1(nums,target,0);
        return res1;
    }
    int sum1=0;
    public void backTracing1(int[] nums,int target,int start){
        if(sum1==target){
            res1.add(new ArrayList<>(path1));//路径的添加有问题
            return;
        }
        for(int i=start;i<nums.length&&sum1+nums[i]<=target;i++) {
            //该算法没有去冲！！
            if (i > start && nums[i] == nums[i - 1]) {
                continue;//去重
            }
            sum1 += nums[i];
            path1.add(nums[i]);
            backTracing1(nums, target, i + 1);
            int temp = path1.getLast();
            sum1 -= temp;
            path1.removeLast();
        }
    }



    List<List<String>> res2=new ArrayList<>();
    List<String> path2=new ArrayList<>();
    StringBuilder sb=new StringBuilder();
    public List<List<String>> partion(String str){
        backing2(str,0,sb);
        return res2;
    }
    public void backing2(String str,int start,StringBuilder sb){
        if(start==str.length()){//回溯结束条件
            res2.add(new ArrayList<>(path2));
            return;
        }
        for(int i=start;i<str.length();i++){
            sb.append(str.charAt(i));//与回溯无疑，只有符合条件的才可以存储
            if(check(sb)){//path存储的是每一个字符串
                path2.add(sb.toString());
                backing2(str,i+1,sb);
                path2.remove(path2.size()-1);
            }
        }
    }
 public boolean check(StringBuilder sb){
        for(int i=0;i<sb.length()/2;i++){
            if(sb.charAt(i)!=sb.charAt(sb.length()-1-i)){
                return false;
            }
        }
        return true;
  }
  List<String> res3=new ArrayList<>();
    List<String> path3=new ArrayList<>();
  public  List<String> ip(String str){
      backing4(str,0,sb4);
      return res3;

  }
  StringBuilder sb4=new StringBuilder();
  public void backing4(String str,int start,StringBuilder sb){
      if(start==str.length()){
          for(int i=0;i<path3.size()-1;i++){
              sb4.append(path.get(i)).append('.');
          }
          sb4.append(path3.get(path3.size()-1));
          res3.add(sb.toString());
      }
      for(int i=start;i<str.length();i++){

      }


  }
}
